1. Field of Invention
The present invention is related to a method for hiding a watermark in images, and more specifically, to a method for hiding a watermark in halftone images.
2. Description of Related Art
Digital halftoning is an approach for transforming multi-tone images into two-tone binary images. These halftone images may resemble the original images when viewed from a distance because of the low-pass nature of the human visual system. Halftoning is commonly used in computer printers, as well as in the printing of books, newspapers, and magazines, since the associated printing processes generate only two tones—black (with ink) and white (without ink). The three most popular halftone techniques are ordered dithering, iteration-based reconstruction, and error diffusion (EDF). Of these, ordered dithering provides an efficient method with the poorest visual quality. The iteration-based reconstruction method offers the best visual quality with the lowest efficiency. Relatively, the EDF method provides a proper solution for balancing the visual quality and the coding efficiency. Therefore, currently available printers usually adopt the EDF halftone printing technique.
Please refer to FIG. 1, which is a schematic diagram showing a conventional EDF halftone printing technique, wherein xi,j represents an input value (or termed as pixel value to be processed presently), vi,j represents a gained value (or termed as a corrected input grayscale value), bi,j represents an output value (or termed as the result after comparing the gained value with a threshold value Vth), ei,j represents an error value produced by deducting the output value bi,j from the gained value vi,j, x′i,j represents error diffusion values for gaining the original input pixel value xi,j, and h represents weight matrix and is the diffusion kernel of EDF printing technique. For example, an EDF kernel of Floyd can be represented as
            1      16        ⁡          [                                    -                                #                                7                                                3                                5                                1                              ]        ,an EDF kernel of Jarvis can be represented as
            1      48        ⁡          [                                    -                                -                                #                                7                                5                                                3                                5                                7                                5                                3                                                1                                3                                5                                3                                1                              ]        ,and an EDF kernel of Stucki can be represented as
            1      42        ⁡          [                                    -                                -                                #                                8                                4                                                2                                4                                8                                4                                2                                                1                                2                                4                                2                                1                              ]        .The entry marked “−” denotes a pixel in the current row which has already been processed (hence diffusing error to it would be pointless), and entry marked “#” denotes the pixel currently being processed. Each numerical entry shows the weighting of the error value ei,j of the pixel presently being processed to be diffused into neighboring pixels. Generally, the relationships of the values xi,j, x′i,j, vi,j, bi,j and ei,j can be formulated as follows:
                              v                      i            ,            j                          =                              x                          i              ,              j                                +                      x                          i              ,              j                        ′                                              (        1        )                                          x                      i            ,            j                    ′                =                              ∑                          m              ,                              n                ∈                R                                              ⁢                                    e                                                i                  +                  m                                ,                                  j                  +                  n                                                      ×                          h                              m                ,                n                                                                        (        2        )                                          b                      i            ,            j                          =                  {                                                                      min_level                  ,                                                                                                  if                    ⁢                                                                                  ⁢                                          v                                              i                        ,                        j                                                                              <                                      v                    th                                                                                                                        max_level                  ,                                                                                                  if                    ⁢                                                                                  ⁢                                          v                                              i                        ,                        j                                                                              ≥                                      v                    th                                                                                                          (        3        )                                                      e                          i              ,              j                                =                                    v                              i                ,                j                                      -                          b                              i                ,                j                                                    ,                            (        4        )            where hm,n represents the entries of the weight matrix h, min_level is the minimum of two pixel values for displaying the halftone image, max_level is the maximum of the two pixel values for displaying the halftone image, and vth is the threshold value.
For instance, in the case by using Floyd's kernel, the equation (2) can be rewritten as follows:
                              x                      i            ,            j                    ′                =                              ∑                          m              =                              -                1                                      0                    ⁢                                    ∑                              n                =                                  -                  1                                            1                        ⁢                                          e                                                      i                    +                    m                                    ,                                      j                    +                    n                                                              ×                              h                                                      1                    -                    m                                    ,                                      2                    -                    n                                                                                                          (        5        )            where the weight matrix h is
      [                                        h                          1              ,              1                                                            h                          1              ,              2                                                            h                          1              ,              3                                                                        h                          2              ,              1                                                            h                          2              ,              2                                                            h                          2              ,              3                                            ]    .
Moreover, if the halftone image is converted from an 8-bit original image, min_level=0 and max_level=255, i.e. 28−1. Accordingly, if the threshold value vth is equal to 128, then the equation (3) can be rewritten as follows:
                              b                      i            ,            j                          =                  {                                                                      0                  ,                                                                                                  if                    ⁢                                                                                  ⁢                                          v                                              i                        ,                        j                                                                              <                  128                                                                                                      255                  ,                                                                                                  if                    ⁢                                                                                  ⁢                                          v                                              i                        ,                        j                                                                              ≥                  128                                                                                        (        6        )            
When bi,j is 0, printer prints an ink-dot on a corresponding ideal pixel square; when bi,j is 255, printer does not print an ink-dot on a corresponding ideal pixel square. The weight matrix h diffuses the error value ei,j between the gained value vi,j and the result bi,j into the adjacent pixel values. Further, the next input value xi,j would be accordingly adjusted to obtain a next gained pixel value vi,j. During performing error diffusion halftoning, the image is scanned from left to right, top to bottom, and the pixel values are quantized one by one. Each time the quantization error is transferred to the neighboring pixels, the pixels that already have been quantized are not affected.
For example, the pseudo-code of Floyd's kernel can be expressed as follows:
            for      ⁢                          ⁢      each      ⁢                          ⁢              i        ⁢                                  /            *      loop      ⁢                          ⁢      through      ⁢                          ⁢      each      ⁢                          ⁢      row      *              /                                  ⁢                                  ⁢        for            ⁢                          ⁢      each      ⁢                          ⁢              j        ⁢                                  /            *      loop      ⁢                          ⁢      through      ⁢                          ⁢      each      ⁢                          ⁢      column      *              /                                  ⁢                                  /            *      performing      ⁢                          ⁢      halftoning      *              /                                  ⁢                                  ⁢        oldpixel              =          pixel      ⁡              (                  i          ,          j                )                                ⁢                            if          ⁢                                          ⁢          oldpixel                ≧        threshold            ,                        then          ⁢                                          ⁢          newpixel                =        max_level                                ⁢                            if          ⁢                                          ⁢          oldpixel                <        threshold            ,                        then          ⁢                                          ⁢          newpixel                =        min_level                                ⁢                  pixel        ⁡                  (                      i            ,            j                    )                    =                                    newpixel            ⁢                                                  ⁢                                                  /                    *          performing          ⁢                                          ⁢          error          ⁢                                          ⁢          diffusion          *                      /                                                  ⁢                                                  ⁢            error_value                          =                  oldpixel          -          newpixel                                        ⁢                  pixel        ⁡                  (                                    i              +              1                        ,            j                    )                    =                        pixel          ⁡                      (                                          i                +                1                            ,              j                        )                          +                              7            /            16                    *          error_value                                        ⁢                  pixel        ⁡                  (                                    i              -              1                        ,                          j              +              1                                )                    =                        pixel          ⁡                      (                                          i                -                1                            ,                              j                +                1                                      )                          +                              3            /            16                    *          error_value                                        ⁢                  pixel        ⁡                  (                      i            ,                          j              +              1                                )                    =                        pixel          ⁡                      (                          i              ,                              j                +                1                                      )                          +                              5            /            16                    *          error_value                                        ⁢                  pixel        ⁡                  (                                    i              +              1                        ,                          j              +              1                                )                    =                        pixel          ⁡                      (                                          i                +                1                            ,                              j                +                1                                      )                          +                              1            /            16                    *          error_value                                        ⁢          endfor      ⁡              (        j        )                  endfor    ⁡          (      i      )      
Recently, secret data hiding in halftone images has become a significant field of research. It is used in many applications, including protecting the ownership rights of an image; preventing the use of an image without permission, and authenticating an image to show that it has not been altered. Numerous methods based on halftones to embed watermarks have been disclosed. For example, Ming Sun Fu and Oscar Chi-Lim Au disclose a method for hiding data in halftone images in their research article “Data hiding in halftone images by stochastic error diffusion” (IEEE ICASSP'01, vol. 3, pp. 1965-1968, 2001). Briefly, the method of Fu and Au generates two halftone images Y0 and Y1 from a single multi-tone image X. The halftone image Y0 is generated by using a standard error diffusion halftoning, and the other halftone image Y1 is generated by using data hiding stochastic error diffusion (DHSED). Information of a hidden watermark H can be obtained by superimposing the two halftone images Y0 and Y1. It is assumed that all of the black pixels of the watermark are defined as a set HB, that all of the white pixels of the watermark are defined as a set HW, and that the pixel currently being processed is represented as (i,j). When (i,j)εHW, the pixel value (y0)i,j of the halftone image Y0 is equal to pixel value (y1)i,j of the halftone image Y1. Alternatively, when (i,j)εHB, Fu and Au define a (2L+1)×(2L+1) square matrix C with the current pixel (i,j) being the center. If the square matrix C includes black pixels and white pixels, then the white pixels in the square matrix C are indicated as a set D, such that D=C∩HBC=C∩HW. When (i,j)∉C, the error value ei,j is set to be zero. When the pixel (i,j)εD the error value ei,j is set to be equal to max(min(vi,j−bi,j, 127), −127). When the pixel (i,j)∉D, the error value ei,j is equal to (vi,j−bi,j). Therefore, (y0)i,j=(y1)i,j while (i,j)εHW, and (y1)i,j has a slight offset from (y0)i,j while (i,j)εHB.
However, the method of Fu and Au has some disadvantages. For example, in order to hide a black pixel of the watermark in the halftone image Y1, it is time-consumed to compare the location of the current pixel (i,j) with location of the black pixel. Further, the contrast of the embedded watermark in the superimposed image is insufficient if the original watermark is a complicated image. Moreover, since the watermark should be a halftone image, the capacity for hiding data is limited to a low level.